BOJ19043 Balance

문제의 제약조건을 정리해보면 LP(선형계획법)형태가 나옵니다. 그런데 그대로 작성해주면 변수(N^2)와 제약(대략 N^2)의 개수가 너무 많기 때문에 TLE를 받을것입니다. 따라서 아래와 같은 관찰을 필요로합니다.

행렬 B가 Balance인 조건을 정리하면 $B_{i,j+1}-B_{i,j}=B_{i+1,j+1}-B_{i+1,j}$가 되고, 이는 임의의 i번째 행에서 인접한 원소(j,j+1)의 차이는 i+1행의 인접한 원소(j,j+1)에서도 동일하다는 의미입니다. 그 차이를 C[j]라고 합시다. 비슷하게 식정리하면 j번째 열에서 인접한 원소(i,i+1)도 모두 같은 값을 가지며, 그 차이를 R[i]라고 합시다. 이제 문제의 조건을 정리해보면 다음과 같습니다.

$B_{r,c}=B_{0,0}+\sum_{0 \leq k \lt r}{R_k}+\sum_{0 \leq k \lt r}{C_k} \geq A_{i,j}$

$Minimize \sum_{0\leq r,c \lt N}{B_{r,c}} = N^2B_{0,0}+N\sum_{0\leq k \lt i \lt N}{R_k}+N\sum_{0\leq k \lt i \lt N}{C_k}$

B[r][c]를 미지수로 두지 않고, B[0][0]하나와 R[i] 그리고 C[i]로 표현해주면 이제 미지수는 O(N)개가 되서 복잡도가 개선되었습니다. 하지만 아직도 (N^2 x 2N)행렬 그대로 simplex solver에 먹이면 TLE날거고 dual시켜서 (2N x N^2)행렬로 계산해주면 됩니다. (simplex의 복잡도가 조건개수에 더 sensitive하기 때문)

근데, 이 상태로는 차이 R[i]가 음수일 수 있는데, 일반적인 Simplex Solver는 x[i]>=0인것을 요구하기 때문에 바로 적용할 수 없습니다. 여기서 일반적인 Trick으로는 자유변수x를 두개의 음이 아닌 변수의 차이 (x0-x1)로 쪼개어 표현하면 x0, x1은 양수조건으로 만들 수 있습니다. 저의 첫 AC제출이 아마 이걸 쓰는거였고, 여기까지만 해도 문제를 해결할 수 있습니다.

변수를 쪼개는건 귀찮으니 그보다 이 문제에서는 A[i][j]>=0조건이 있기 때문에 이를 활용하기 위해 아래와 같이 식을 다시 써줍시다. B[0][0]을 예외처리하기 싫어서 자유변수 R[-1]과 C[-1]을 도입하여 PR[0]=R[-1], PC[0]=C[-1], PR[0]+PC[0]=R[-1]+C[-1]=B[0][0] 이 되도록 정리하였음.

$PR_i = \sum_{-1\leq k \lt i}{R_k}$

$PC_i = \sum_{-1\leq k \lt i}{C_k}$

$B_{r,c} = PR_r + PC_c \geq A_{r,c}$

$Minimize N\sum_{0\leq i \lt N}{PR_i}+N\sum_{0\leq i \lt N}{PC_i}$

목적함수의 Cost(계수)가 모든 변수에 대해 N으로 동일하기 때문에, 그리고 PR[r]+PC[c]>=A[r][c]제약조건에서 A[r][c]가 양수이기 때문에, 조건의 두 변수 중 하나가 음수인 최적해는 항상 동일한 cost의 두 변수가 음이 아닌 해가 존재합니다. 음,, 이게 막 자명한건 아닌데, 직관적으로 그럴거같고 아무튼 제출해보면 맞습니다. 따라서 이제 위에서 정리한 LP식을 Simplex로 돌려주면 답을 구할 수 있습니다. 참고로 여기까지 정리한 식은 BOJ1281번과 (거의)똑같은 형태라서 Dual해보면 Hungarian이 가능합니다.

코드: http://boj.kr/a83df8b8238847c7a00b12a474cfbe3d